//
// Created by lanlu on 2025/8/14.
//

#include <unordered_set>
#include <vector>
using namespace std;

// 并查集
class UnionFind {
private:
    // 存储元素父节点的数组
    vector<int> parent;
    // 存储集合的大小
    vector<int> size;
public:
    // 初始化 传入元素个数n
    UnionFind(int n)
    {
        parent.resize(n);
        // 初始每个集合的大小为1
        size.resize(n,1);
        for (int i = 0; i < n; i++)
        {
            // 每个元素自成集合 父节点指向自身
            parent[i] = i;
        }
    }

    // 查找根节点
    int find(int x)
    {
        // 如果当前元素的父节点不是自身 则继续查找
        // 如果当前元素的父节点是自身 则找到根 直接返回
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并
    void merge(int x, int y)
    {
        // 如果两个元素在同一个集合中 则不需要合并
        // 否则将两个元素所在集合的根节点指向同一个元素
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;

        // 小的集合合并到较大的集合中
        if (size[rootX] < size[rootY])
        {
            swap(rootX, rootY);
        }

        parent[rootY] = rootX;
        size[rootX] += size[rootY];
    }

    // 判断是否在同一个集合中
    bool isConnected(int x, int y)
    {
        return find(x) == find(y);
    }

    // 获取集合的数量
    int getCount(int x)
    {
        return size[find(x)];
    }
};

class Solution {
public:
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        // 将properties中每个一维数组 对应一个顶点 即为并查集的初始化
        // 相邻两个一维数组的交集个数 和k比较 如果>=k 则合并
        // 连通分量的个数 就是集合的个数
        int n = properties.size();
        UnionFind uf(n);
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (getIntersection(properties[i], properties[j]) >= k)
                {
                    uf.merge(i,j);
                }
            }
        }

        // 计算集合的个数
        unordered_set<int> roots;
        for (int i = 0; i < n; i++)
        {
            // 找到每个元素的根节点
            roots.insert(uf.find(i));
        }
        return roots.size();
    }

    // 求交集的个数 即为共有的不同整数的数量
    int getIntersection(vector<int>& a, vector<int>& b)
    {
        // 将一个数组放入set
        unordered_set<int> setA(a.begin(), a.end());
        int cnt = 0;
        for (int num : b)
        {
            // 如果num在setA和vectorB中都存在 则cnt++
            if (setA.count(num))
            {
                cnt++;
                // 从set中删除 使得相同整数只计算一次
                setA.erase(num);
            }
        }
        return cnt;
    }
};